#include "avl.h"

AVL::AVL() { root = nullptr; }

static int max(int a, int b) {
    if(a > b) return a;
    return b;
}

//分配一个新的节点
AVLnode<pair<string, string> >* AVL::newNode(string key, string value) {
  AVLnode<pair<string, string> >* Node = new AVLnode<pair<string, string> >(make_pair(key, value));
    return Node;
}

//获取当前节点的高度
int AVL::getHeight(AVLnode<pair<string, string> >* u) {
    if(!u) return 0;
    return u->height;
}

//获取当前节点的平衡因子
int AVL::getBalenceFactor(AVLnode<pair<string, string> > *u) {
        if(!u) return 0;
    return getHeight(u->lchild) - getHeight(u->rchild);  //平衡因子 = 左子树的高度 - 右子树的高度
}

//在进行插入，删除操作的同时对调整节点的高度进行更新
void AVL::updataHeight(AVLnode<pair<string, string> > *&u) {  //当前节点的高度 = max(左子树的高度，右子树的高度)
    u->height = max(getHeight(u->lchild), getHeight(u->rchild)) + 1;
}

//返回根节点
AVLnode<pair<string, string> >* AVL::getRoot() {
    return root;
}

//返回键值
string AVL::getKey(AVLnode<pair<string, string> > *u) {
    return u->value.first;
}

//返回Second值
string AVL::getValue(AVLnode<pair<string, string> > *u) {
    return u->value.second;
}

//AVL树中的查找函数
void AVL::search(AVLnode<pair<string, string> > *u, string key) {
    //如果该节点为空节点的话，那么说明搜索到树的底层也没有找到节点，空树查找失败
    if(!u) {
        res = "未找到该单词";
        return ;
    }
    //如果等于这个单词的key值的话，说明找到改值
    if(key == u->value.first) {
        res = u->value.second;
        return ;
    } else if(key < u->value.first) {  //如果当前节点的key值的字典序是小于key值的，那么向左子树进行递归
        search(u->lchild, key);
    } else { //如果当前节点的key值的字典序是大于key值的，那么向右子树进行递归
        search(u->rchild, key);
    }
}

//提供参数更少的接口
void AVL::search(string key) {
    search(root, key);
}

//通过左旋来对AVL树进行调整高度
AVLnode<pair<string, string> >* AVL::leftRotate(AVLnode<pair<string, string> >* u) {
  //temp指向当前节点的右子树
  AVLnode<pair<string, string> >* temp = u->rchild;
  //调制的节点的右子树指向他右子树的左子树
  u->rchild = temp->lchild;
  //让右子树的左子树指向需要调制的节点
  temp->lchild = u;
  //更新调整的两个节点的高度，而他们的子树的高度并未发生该变
  updataHeight(u);
  updataHeight(temp);
  return temp;
}

//通过右旋来对AVL树进行调整高度
AVLnode<pair<string, string> >* AVL::rightRotate(AVLnode<pair<string, string> >* u) {
  //temp指向当前节点的左子树
  AVLnode<pair<string, string> > *temp = u->lchild;
  //让调制节点的左子树指向他的左节点的右子树
    u->lchild = temp->rchild;
  //让temp的右子树指向当前节点
  temp->rchild = u;
    //调整平衡树的高度
    updataHeight(u);
  updataHeight(temp);
  return temp;
}

//AVL树的插入操作
AVLnode<pair<string, string> >* AVL::insert(AVLnode<pair<string, string> >* &u, string key, string value) {
    if(!u) return newNode(key, value); //到达了一个空节点，对新的节点分配内存并赋值
    //key值小于当前节点的key值，向左进行递归, 反之亦然
    if(key < u->value.first) u->lchild = insert(u->lchild, key, value);
    else if(key > u->value.first) u->rchild = insert(u->rchild, key, value);
    updataHeight(u);
    int balance = getBalenceFactor(u);
    if(balance > 1 && getBalenceFactor(u->lchild) >= 0) return rightRotate(u);
    if(balance < -1 && getBalenceFactor(u->rchild) <= 0) return leftRotate(u);
    if(balance > 1 && getBalenceFactor(u->lchild) < 0) {
        u->lchild = leftRotate(u->lchild);
        return rightRotate(u);
        }
        if(balance < -1 && getBalenceFactor(u->rchild) > 0) {
            u->rchild = rightRotate(u->rchild);
            return leftRotate(u);
        }
        return u;
}

//对insert函数进行重载，减少传入函数的参数
void AVL::insert(string key, string value) {
    search(key);
    if(res == "未找到该单词")
  root = insert(root, key, value);
}

//AVL树的删除操作
AVLnode<pair<string, string> >* AVL::deleteNode(AVLnode<pair<string, string> >* u, string key) {
  if(!u) return nullptr;
  AVLnode<pair<string, string> >* ret;
  if(key < u->value.first) {
    u->lchild = deleteNode(u->lchild, key);
    ret = u;
    } else if(key > u->value.first) {
        u->rchild = deleteNode(u->rchild, key);
        ret = u;
    } else {
        if(!u->rchild) {
            AVLnode<pair<string, string> >* temp = u->lchild;
            u->lchild = nullptr;
            delete u;
            ret = temp;
        } else if(!u->lchild) {
            AVLnode<pair<string, string> >* temp = u->rchild;
            u->rchild = nullptr;
            delete u;
            ret = temp;
        } else {
            AVLnode<pair<string, string> >* q = nullptr;
            for(q = u->rchild; q->lchild; q = q->lchild);
            q->rchild = deleteNode(q->rchild, q->value.first);
            q->lchild = u->lchild;
            u->lchild = u->rchild = nullptr;
            delete u;
            ret = q;
        }
    }
    //对高度进行调整
    if(!ret) return nullptr;
    updataHeight(ret);
    int balance = getBalenceFactor(ret);
    // LL
    if(balance > 1 && getBalenceFactor(ret->lchild) >= 0) return rightRotate(ret);
    // RR
    if(balance < -1 && getBalenceFactor(ret->rchild) <= 0) return leftRotate(ret);
    // LR
    if(balance > 1 && getBalenceFactor(ret->lchild) < 0) {
        ret->lchild = leftRotate(ret->lchild);
        return rightRotate(ret);
    }
    // RL
    if(balance < -1 && getBalenceFactor(ret->rchild) > 0) {
        ret->rchild = rightRotate(ret->rchild);
        return leftRotate(ret);
    }
    return ret;
}

//对函数进行重载，进而将函数传入的参数减少
void AVL::deleteNode(string key) {
    search(key);
    if(res == "未找到该单词") return ;
  root = deleteNode(root, key);
}

void AVL::postInorder(AVLnode<pair<string, string> >* &u) {
  if(u->lchild) postInorder(u->lchild);
  if(u->rchild) postInorder(u->rchild);
  delete u;
}

//析构函数
AVL::~AVL() {
    if(root)
  postInorder(root);
}

//调试用的
//void AVL::dfs(AVLnode<pair<string, string> >* u) {
//	if(u->lchild) dfs(u->lchild);
//	cout << u->value.first << '\n';
//	if(u->rchild) dfs(u->rchild);
//}
